package com.javademo;

import java.util.*;

public class RandomizedSet {
    private Map<Integer, Integer> map; // 存储元素及其在列表中的位置
    private List<Integer> list; // 存储元素
    private Random random; // 用于生成随机数

    public RandomizedSet() {
        this.map = new HashMap<>();
        this.list = new ArrayList<>();
        this.random = new Random();
        //dddddddddddddd
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false; // 元素已存在，返回 false
        }
        map.put(val, list.size());
        list.add(val);
        return true; // 插入成功，返回 true
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false; // 元素不存在，返回 false
        }
        int index = map.get(val);
        int lastElement = list.get(list.size() - 1);
        list.set(index, lastElement); // 将最后一个元素移到被删除元素的位置
        map.put(lastElement, index);
        list.remove(list.size() - 1); // 移除最后一个元素
        map.remove(val);
        return true; // 删除成功，返回 true
    }

    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex); // 返回随机元素
    }
}
